#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_DICT_SIZE 4096
#define ASCII_SIZE 256
#define MAX_CODE_SIZE 12 // 假设最大码字长度为12位

typedef struct
{
    unsigned int code;
    char str[256];
} DictEntry;

DictEntry dict[MAX_DICT_SIZE];
unsigned int dictSize = ASCII_SIZE; // 初始字典大小为ASCII字符数

void initDictionary()
{
    for (unsigned int i = 0; i < ASCII_SIZE; ++i)
    {
        dict[i].code = i;
        dict[i].str[0] = (char)i;
        dict[i].str[1] = '\0';
    }
}

unsigned int readCode(FILE *inputFile)
{
    unsigned int code = 0;
    int bit;
    for (int i = 0; i < MAX_CODE_SIZE; ++i)
    {
        bit = fgetc(inputFile);
        if (bit == EOF)
        {
            return EOF;
        }
        code = (code << 1) | (bit & 1);
    }
    return code;
}

void addEntry(const char *str)
{
    if (dictSize < MAX_DICT_SIZE)
    {
        dict[dictSize].code = dictSize;
        strcpy(dict[dictSize].str, str);
        dictSize++;
    }
}

void lzwDecompress(FILE *inputFile, FILE *outputFile)
{
    unsigned int oldCode = readCode(inputFile);
    unsigned int newCode;
    char string[256];
    char character;

    if (oldCode == EOF)
    {
        return; // 空文件
    }

    character = (char)oldCode;
    fputc(character, outputFile);
    string[0] = character;
    string[1] = '\0';

    while ((newCode = readCode(inputFile)) != EOF)
    {
        DictEntry *entry = &dict[newCode];
        if (entry->code == 0)
        {
            // 字典中没有新代码，需要构建
            entry->code = dictSize;
            strcpy(entry->str, string);
            strcat(entry->str, string);
            fputc(entry->str[0], outputFile);
            addEntry(entry->str);
        }
        else
        {
            // 字典中有新代码
            fputc(entry->str[0], outputFile);
            strcpy(string, entry->str);
            strcat(string, &character);
            addEntry(string);
        }
        character = entry->str[0];
    }
}

int main()
{
    FILE *inputFile = fopen("compressed.lzw", "rb"); // 以二进制模式读取
    FILE *outputFile = fopen("output.txt", "w");

    if (inputFile == NULL)
    {
        perror("Error opening input file");
        return 1;
    }

    if (outputFile == NULL)
    {
        perror("Error opening output file");
        fclose(inputFile);
        return 1;
    }

    initDictionary();
    lzwDecompress(inputFile, outputFile);

    fclose(inputFile);
    fclose(outputFile);
    return 0;